import java.util.Collections;
import java.util.PriorityQueue;
//力扣295. 数据流的中位数
class MedianFinder {
    // 最大堆存储较小的一半数字（Java的PriorityQueue默认是最小堆，所以用反转比较器）
    private PriorityQueue<Integer> maxHeap;
    // 最小堆存储较大的一半数字
    private PriorityQueue<Integer> minHeap;

    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        // 1. 先加入最大堆
        maxHeap.offer(num);
        // 2. 将最大堆的最大值移到最小堆
        minHeap.offer(maxHeap.poll());
        // 3. 如果最小堆比最大堆大，平衡两个堆
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        } else {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }
}


//力扣121. 买卖股票的最佳时机
class Solution {
    public int maxProfit(int[] prices) {
        int minNum = Integer.MAX_VALUE;
        int ans = 0;
        for(int i=0;i<prices.length;i++){
            if(minNum>prices[i]){
                minNum = prices[i];
            }
            ans = Math.max(ans,prices[i]-minNum);
        }
        return ans;
    }
}


//力扣55. 跳跃游戏
class Solution1 {
    public boolean canJump(int[] nums) {
        int maxReach = 0; // 最远到达的下标
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) {
                return false;
            }
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        return true;
    }
}